package com.iceph0x.algorithm.sort;

import java.util.Comparator;

import com.iceph0x.algorithm.framework.ISort;

public class ShellSort implements ISort {

    int[] gap = new int[] { 1, 4, 10, 23, 57, 132, 301, 701, 1750 };
    
    @Override
    public void sort(int[] data) {
        if (data == null || data.length < 2)
            return;

        if (data.length > 5000) {
            System.out.println("ShellSort::need to modify gap array to prompt performance.");
        }
        
        int gapIndex = gap.length - 1;
        while (gap[gapIndex] >= data.length)
            -- gapIndex;
        
        while (gapIndex >= 0) {
            for (int i = gap[gapIndex], temp; i < data.length; ++i) {
                temp = data[i];
                int j = i - gap[gapIndex];
                while (j >= 0 && data[j] > temp) {
                    data[j + gap[gapIndex]] = data[j];
                    j -= gap[gapIndex];
                }
                data[j + gap[gapIndex]] = temp;
            }
            --gapIndex;
        }
    }
    
    private void swap(int[] data, int i, int j) {
        if (data[i] == data[j])
            return;
        
        data[i] ^= data[j];
        data[j] ^= data[i];
        data[i] ^= data[j];
    }

    @Override
    public void sort(Object[] data, Comparator<Object> c) {
        // TODO Auto-generated method stub

    }
}
